package com.future;

import com.future.util.TreeNode;

import java.util.LinkedList;

/**
 * Description: 449. 序列化和反序列化二叉搜索树(类似297. 二叉树的序列化与反序列化)
 *
 * @author weiruibai.vendor
 * Date: 2023/1/3 10:04
 */
public class Solution_449 {

    private static Codec instance = new Codec();

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        root = null;
        String serial = instance.serialize(root);
        System.out.println(serial);
        TreeNode deserialize = instance.deserialize(serial);
        System.out.println(deserialize);
    }
}

class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preSearch(root, sb);
        return sb.toString();
    }

    private void preSearch(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(".null");
            return;
        }
        sb.append("." + root.val);
        preSearch(root.left, sb);
        preSearch(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split("\\.");
        LinkedList linked = new LinkedList();
        for (String str : split) {
            if ("".equals(str)) continue;
            linked.add(str);
        }
        return processDeserialize(linked);
    }

    private TreeNode processDeserialize(LinkedList<String> linked) {
        if (linked.isEmpty() || linked.peek().equals("null")) {
            linked.poll();
            return null;
        }
        String val = linked.poll();
        TreeNode head = new TreeNode(Integer.valueOf(val));
        head.left = processDeserialize(linked);
        head.right = processDeserialize(linked);
        return head;
    }
}